/*
 * @Author: liusheng
 * @Date: 2022-04-22 22:58:31
 * @LastEditors: liusheng
 * @LastEditTime: 2022-04-23 11:03:18
 * @Description: 剑指 Offer II 039. 直方图最大矩形面积
 * email:liusheng613@126.com
 * Copyright (c) 2022 by liusheng/liusheng, All Rights Reserved. 
 * 
 剑指 Offer II 039. 直方图最大矩形面积
给定非负整数数组 heights ，数组中的数字用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。

求在该柱状图中，能够勾勒出来的矩形的最大面积。

 

示例 1:



输入：heights = [2,1,5,6,2,3]
输出：10
解释：最大的矩形为图中红色区域，面积为 10
示例 2：



输入： heights = [2,4]
输出： 4
 

提示：

1 <= heights.length <=105
0 <= heights[i] <= 104
 

注意：本题与主站 84 题相同： https://leetcode-cn.com/problems/largest-rectangle-in-histogram/
 */

#include "header.h"

class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        //Area will be calculated for previous index
        //Appending zero to calculate till end
        heights.push_back(0); 
        int n = heights.size();
        
        //use monototic increasing stack to construct a array 
        // which holds the index of the height by ascending order
        stack<int> monotonicIncrSt;
        int result = 0;
        for (int i = 0; i < n; ++i)
        {
            while (!monotonicIncrSt.empty() && heights[i] < heights[monotonicIncrSt.top()])
            {
                int h = heights[monotonicIncrSt.top()];
                monotonicIncrSt.pop();

                int w = 0;
                if (monotonicIncrSt.empty())
                {
                    w = i;
                }
                else 
                {
                    //the monototicIncrSt.top() is previous smaller than h
                    //h[i] is the next smaller than h
                    w = i - monotonicIncrSt.top() - 1;
                }
                result = max(result,w * h);
            }
            monotonicIncrSt.push(i);
        }

        return result;
    }
};

//same as above solution,but not modified the origin parameter heights
class Solution {
public:
    int largestRectangleArea(vector<int>& heights) { 
        //Area will be calculated for previous index
        //Appending zero to calculate till end
        // heights.push(0);
        int n = heights.size();
        stack<int> monotonicIncrSt;
        int result = 0;
        for (int i = 0; i < n; ++i)
        {
            //heights[i] is first element smaller than the stack
            //top index height(next smaller)
            //value in stack has been sorted ascending,so top's
            //previous smaller index is the previous value in stack
            //or no element small than it,the width will be the index i
            while (!monotonicIncrSt.empty() && heights[i] < heights[monotonicIncrSt.top()])
            {
                int height = heights[monotonicIncrSt.top()];
                monotonicIncrSt.pop();
                int width = monotonicIncrSt.empty() ? i : i - monotonicIncrSt.top() - 1;
                // printf("000 height:%d,width:%d\n",height,width);
                result = max(result,width * height);
            }
            monotonicIncrSt.push(i);
        }
        
        //the thought is same as above
        //deal with the remaining value in stack
        //here the top index in stack's value in heights[index]
        //is no element greater after it,so notice the width's value will be n or n - presmallIndex - 1
        while (!monotonicIncrSt.empty()) {
            int height = heights[monotonicIncrSt.top()];
            monotonicIncrSt.pop();
            int width = monotonicIncrSt.empty() ? n : n - monotonicIncrSt.top() - 1;
            // printf("111 height:%d,width:%d\n",height,width);
            result = max(result,width * height);
        }
        return result;
    }
};
